package sort;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.ConcurrentSkipListSet;

/**
 * @Author: Hugh
 * @Date: 2021/3/2
 */
public class SkipList {
    private SkipListNode head;
    private int maxLevel;
    private int size;
    private static final double PROBABILITY = 0.5;

    public SkipList() {
        size = 0;
        maxLevel = 0;
        head = new SkipListNode(null);
        head.nextNodes.add(null);
    }
//    ConcurrentSkipListSet
    public SkipListNode getHead() {
        return head;
    }


    // Returns the skiplist node with greatest value <= e
    private SkipListNode find(Integer e) {
        return find(e, head, maxLevel);
    }

    // Returns the skiplist node with greatest value <= e
    // Starts at node start and level
    private SkipListNode find(Integer e, SkipListNode current, int level) {
        do {
            current = findNext(e, current, level);
        } while (level-- > 0);
        return current;
    }

    // Returns the node at a given level with highest value less than e
    // 关键方法：找到给定level中value小于e的最大节点
    private SkipListNode findNext(Integer e, SkipListNode current, int level) {
        SkipListNode next = current.nextNodes.get(level);
        while (next != null) {
            Integer value = next.value;
            if (lessThan(e, value)) { // e < value
                break;
            }
            current = next;
            next = current.nextNodes.get(level);
        }
        return current;
    }


    public void add(Integer newValue) {
        if (!contains(newValue)) {
            size++;
            int level = 0;
            while (Math.random() < PROBABILITY) {
                level++;
            }
            while (level > maxLevel) {
                head.nextNodes.add(null);
                maxLevel++;
            }
            SkipListNode newNode = new SkipListNode(newValue);
            SkipListNode current = head;
            do {
                current = findNext(newValue, current, level);
                newNode.nextNodes.add(0, current.nextNodes.get(level));
                current.nextNodes.set(level, newNode);
            } while (level-- > 0);
        }
    }

    public boolean contains(Integer value) {
        SkipListNode node = find(value);
        return node != null && node.value != null && equalTo(node.value, value);
    }

    public void delete(Integer deleteValue) {
        if (contains(deleteValue)) {
            SkipListNode deleteNode = find(deleteValue);
            size--;
            int level = maxLevel;
            SkipListNode current = head;
            do {
                current = findNext(deleteNode.value, current, level);
                if (deleteNode.nextNodes.size() > level) {
                    current.nextNodes.set(level, deleteNode.nextNodes.get(level));
                }
            } while (level-- > 0);
        }
    }
    // Inner Class
    public static class SkipListIterator implements Iterator<Integer> {
        SkipList list;
        SkipListNode current;

        public SkipListIterator(SkipList list) {
            this.list = list;
            this.current = list.getHead();
        }

        @Override
        public boolean hasNext() {
            return current.nextNodes.get(0) != null;
        }

        @Override
        public Integer next() {
            current = current.nextNodes.get(0);
            return current.value;
        }
    }

    public Iterator<Integer> iterator() {
        return new SkipListIterator(this);
    }

    private boolean lessThan(Integer a, Integer b) {
        return a.compareTo(b) < 0;
    }

    private boolean equalTo(Integer a, Integer b) {
        return a.compareTo(b) == 0;
    }

    public static class SkipListNode {
        public Integer value;
        public ArrayList<SkipListNode> nextNodes;

        public SkipListNode(Integer value) {
            this.value = value;
            nextNodes = new ArrayList<SkipListNode>();
        }
    }
}
